package linkedList;
//实现不带傀儡节点的单向链表
public class LinkedList implements ILinkedListOperation{
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
    public int size;
    /**
     * 实现：
     * addFirst（尾插）
     * addLast（头插）
     * remove（删除指定元素节点）
     * size（获取链表长度）
     * contains（判断链表中是否存在key）
     * clear（清空链表）*/

    @Override
    public boolean addFirst(int val) {
        ListNode node = new ListNode(val);
        if(isEmpty()) {
            this.head = node;
            this.last = this.head;
        } else {
            node.next = this.head;
            this.head = node;
        }
        this.size++;
        return true;
    }

    @Override
    public boolean addLast(int val) {
        ListNode node = new ListNode(val);
        if(isEmpty()) {
            this.head = node;
            this.last = this.head;
        } else {
            this.last.next = node;
            this.last = node;
        }
        this.size++;
        return true;
    }

    @Override
    public boolean remove(int key) {
        if(isEmpty()) {
            System.out.println("当前链表为空！");
            return false;
        }
        int retIndex = findKey(key);
        if(retIndex<0) {
            System.out.println("抱歉，链表中不存在该值！");
            return false;
        } else {
            if(retIndex==0) {
                //头删
                this.head = this.head.next;
            } else {
                //如果不是删除头节点 代码此时链表至少存在2个以上节点
                //此时需要找前一个节点
                ListNode cur = this.head;
                while(retIndex-1!=0) {
                    cur = cur.next;
                    retIndex--;
                }
                ListNode del = cur.next;
                cur.next = del.next;
            }
            this.size--;
            return true;
        }
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean contains(int key) {
        return findKey(key)>=0;
    }

    @Override
    public void clear() {
        //一个节点一个节点删除 并且释放所有引用的对象 避免内存泄露
        ListNode cur = this.head;
        while(cur!=null) {
            ListNode nextNode = cur.next;
            cur.next = null;
            //cur.val = null;
            cur = nextNode;
            this.size--;
        }
        this.head = null;
        this.last = null;
    }

    //打印链表-用于调试
    public void display() {
        if (isEmpty()) {
            return;
        }
        ListNode cur =this.head;
        while(cur!=null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //判空
    private boolean isEmpty() {
        return this.size==0;
    }

    //查找某个元素并返回其下标
    private int findKey(int key) {
        if(isEmpty()) {
            return -1;
        }
        ListNode cur = this.head;
        for(int i = 0; i < this.size; i++) {
            if(cur.val==key) {
                return i;
            }
            cur = cur.next;
        }
        return -1;
    }
}
